#include <vector>
#include <algorithm>
using std::vector;


class Solution {
public:
    //三数之和
    
    //注意这里可以把求nums[i]+nums[j]+nums[k]==0转换为：nums[i] == -(nums[j]+nums[k])
    //这样就可以对[j,k]区间使用双指针算法了
    //如果数组是单调的就要想到的是：双指针、二分查找
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> vv;
        std::sort(nums.begin(),nums.end());
        int size = nums.size();
        for(int i = 0;i<=size-3;++i)
        {
            int val = nums[i];
            int left_p = i+1;
            int right_p = size-1;
            while(left_p < right_p)//根据题意找到的三数的下标必须要不同
            {
                int tmp1 = nums[left_p];
                int tmp2 = nums[right_p];
                if((tmp1+tmp2) > (-val))
                --right_p;
                else if((tmp1+tmp2) < (-val)) 
                ++left_p;
                else if((tmp1+tmp2) == (-val))
                {
                    vv.push_back({val,nums[left_p],nums[right_p]});
                    while(tmp1 == nums[left_p] || tmp2 == nums[right_p])
                    {
                        if(left_p >= right_p)
                        goto back;
                        if(tmp1 == nums[left_p])
                        ++left_p;
                        if(tmp2 == nums[right_p])
                        --right_p;
                    }
                }
            }
            back:
            while((i+1 <= size-3) && (val == nums[i+1]))
            ++i;
        }
        return vv;
    }
};
